package com.linearList;

/**
 * @Author: linKe
 * @Date: 2021/12/29 23:04
 * @FileName: SeqList
 * @version: 1.0
 * @Description: 线性表顺序存储结构
 * 顺序表类，泛型类
 */
public class SeqList<T> {

    /**对象数组*/
    Object[] element;

    /**对象个数（长度）*/
    int n;

    /**构造容量为length的空表）*/
    public SeqList(int length){
        //申请数组的存储空间，元素为null
        this.element= new Object[length];
        this.n=0;
    }

    /**构造方法重载（默认生成一个长度为64的空表）*/
    public SeqList(){  //创建默认容量的空表
        //调用本类已声明的指定参数列表的构造方法
        this(64);
    }

    /**由values数组提供元素*/
    public SeqList(T[] values){//构造顺序表，由values数组提供元素，忽略其中空对象
        //创建容量为values.length的空表
        this(values.length);
        //创建容量为values.length的空表
        for (int i = 0; i < values.length; i++) {
            //复制数组元素，O（n）
            //对象引用赋值
            this.element[i]=values[i];
        }
        this.n=element.length;
    }

    /**其他成员方法*/
    public boolean isEmpty(){
        //判断顺序表是够为空，若空返回true，O（1）时间复杂度
        return this.n == 0;
    }

    /**返回元素的个数*/
    public int size(){
        //返回顺序表元素个数 ,O（1）时间复杂度
        return this.n;
    }

    /**
     * 顺序表成员方法
     * 返回第i个元素,o≤i<n。若i越界，返回null O（1）
     * @param i 元素下标
     * @return  结果
     */
    public T get(int i){
        if(i>=0 && i<this.n) {
            //返回数组元素引用的对象，传递对象引用
            return (T)this.element[i];
        }
        return null;
    }

    /**
     * 设置第i个元素为x，o≤i<n。若i越界，
     * 抛出序号越界异常：若x==null，抛出空对象异常。o（1）
     * @param i 元素下标
     * @param x 元素值
     */
    public void set(int i,T x){
        if (x == null){
            //抛出空对象异常
            throw new NullPointerException("x==null");
        }
        if (i>=0 && i<this.n){
            //当前下标位置元素赋值
            this.element[i]=x;
        }else {
            //抛出序号越界异常
            throw new java.lang.IndexOutOfBoundsException(i+"");
        }

    }

    /**
     * 返回顺序表所有元素的描述字符串，
     * 形式为“（，）”。覆盖Object类的toString（）方法
     * @return  重写toString方法
     */
    @Override
    public String toString(){
        //返回类名
        String str = this.getClass().getName()+"(";
        if (this.n>0){
            //执行T类的toString（）方法，运行时多态
            //第0个元素的拼接
            str += this.element[0].toString();
        }
        for (int i = 1; i < this.n; i++) {
            //执行T类的toString（）方法，运行时多态
            //循环到元素i
            str += ","+this.element[i].toString();
        }
        //空表返回（）
        return str+")";
    }

    /**
     * 插入x作为第i个元素，x!=null，返回x序号。
     * 若x==null，抛出空对象异常。 O（n）
     * @param i 下标位置
     * @param x 元素值
     * @return  结果
     */
    public int insert(int i,T x){
        if (x==null){
            //抛出空对象异常
            throw new NullPointerException("x==null");
        }
        if (i<0){
            //插入位置i容错，插入在最前
            i=0;
        }
        if (i>this.n){
            //插入到最后
            i=this.n;
        }
        //数组变量引用赋值，source也引用element数组
        Object[] source = this.element;
        //若数组满,则扩充顺序表的数组容量
        if (this.n == element.length){
            //数组扩容 重新申请一个容量更大的数组
            this.element = new Object[source.length*2];
            //复制当前数组前i-1个元素
            for (int j = 0; j < i; j++) {

//              复制对象写错了  this.element[i] = source[i];
                this.element[j] = source[j];
            }
        }
        //从i开始至表尾的元素向后移动，次序从后向前
        for (int j = this.n-1; j >= i; j--) {
//        for (int j = 0; j < i; j++) {
            //这里的逻辑 将前一个值赋给下一个node值   中间的元素值会循环成初始值11
            this.element[j+1] = source[j];
        }
        this.element[i] = x;
        //数组长度加1
        this.n++;
        //返回x序号
        return i;
    }

    /**
     * 在表尾插入元素
     * @param x 元素值
     * @return  结果
     */
    public int insert(T x){
       return this.insert(this.n,x);
    }

    /**
     * 删除第i个元素，0≤i<n，返回被删除元素。
     * 若i越界，返回null。
     * @param i 元素下标
     * @return  结果
     */
    public T remove(int i){
        //判断i下标的元素是否存在  并且数组不会空
        if (this.n>0 && i>=0 && i<this.n){
            //old中存储被删除元素
            T old = (T)this.element[i];
            for (int j = i; j < this.n-1; j++) {
                //元素前移一个位置
                this.element[j] = this.element[j+1];
            }
            //设置数组元素最后一位对象为空，释放原引用实例
            this.element[this.n-1] = null;
            //数组长度减一
            this.n--;
            //返回old局部变量引用的对象，传递对象引用
            return old;
        }
        return null;
    }

    /**
     * 搜索首次出现的与key相等元素，返回元素序号i，0≤i<n;查找不成功返回-1。
     * @param key  搜索元素值
     * @return  结果下标
     */
    public int search(T key){
        //遍历数组对象
        for (int i = 0; i < this.n; i++) {
            //执行T类的equals（Object）方法，运行时多态
            //进行结果比较，最先出现的相等元素，直接返回
            if(key.equals(this.element[i])){
                return i;
            }
        }
        //空表或未找到时
        return -1;
    }

    /**
     * 重写equals方法
     * 比较两个顺序表是否相等。覆盖。 O（n）
     * @param obj   比较对象
     * @return  结果
     */
    @Override
    public boolean equals(Object obj){
        //若this和obj引用同一个顺序表实例，则相等
        if (this == obj){
            return true;
        }
        //若obj引用顺序表实例。SeqList<?>是所有SeqList<T>的父类

        if (obj instanceof SeqList<?>){
            //声明list也引用obj引用的实例
            SeqList<T> list = (SeqList<T>) obj;
            //比较两者长度是否相等
            if (this.n == list.n){
                //比较两个顺序表的所有元素是否相等
                for (int i = 0; i < this.n; i++) {
                    //equals（Object）运行时多态 重写了equals方法
                    if (!(this.get(i).equals(list.get(i)))){
                        //不相等时，返回false否则true
                        return false;
                    }
                }
                return true;
            }
        }
        return false;
    }


}
